This invention relates to a method which facilitates reasoning about route selection in circuit- and packet-switched communication networks, and more particularly to networks represented by a blocking island (xe2x80x9cBIxe2x80x9d) abstraction.
Blocking Island abstractions facilitate reasoning concerning the different routes that a transmittable data stream might take. The BI is a part of a communication network in which routing demands on limited resources (which are sometimes referred to herein as bandwidths or bandwidth levels, the use of such specific terms hereinafter being intended as interchangeable with the more general term xe2x80x9crestrictive costsxe2x80x9d) not larger than Beta (xe2x80x9cxcex2xe2x80x9d) is possible. Using the BI abstraction, it is possible to construct a hierarchy of simplified network graphs, called a Blocking Island Hierarchy (xe2x80x9cBIHxe2x80x9d). Each of these graphs, called Blocking Island Graphs (xe2x80x9cBIGsxe2x80x9d), is defined by the set of BIs for a particular xcex2. In other words, a BI defines an equivalence class of potential paths with a bandwidth of up to xcex2. B, an input parameter for a method of constructing a BIH, denotes the finite set of possible values for xcex2. B is an ordered set. Consequently, the resulting BIH is a discrete abstraction of a communication network.
The usefulness of BIs (and the concepts built upon them) results from their fundamental properties, such as unicity, partitioning, bottleneck identification, route existence, route location and inclusion. However, the applicability of discrete BIHs is limited because of their limited precision due to the BIHs"" discretization. For instance, networks like ATM and IP that provide circuits in an almost continuous range (due to a small cell or packet size) would require either discretization or a large set of B. The latter is impractical, as most xcex2-BIGs would consume memory without providing insightxe2x80x94defeating the very purpose of constructing such an abstraction. Further ore, the routing method presented by Christian Frei and Boi Faltings in xe2x80x9cA Dynamic Hierarchy of Intelligent Agents for Network Managementxe2x80x9d, Proceedings of the Second International Workshop on intelligent Agents for Telecom Applications (IATA ""98), Paris, France, 1998, the content of which is incorporated by reference, is only applicable for demands with bandwidth requirements within the set B.
Resource management (including routing and connection admission control) in general plays an important role in network planning and control, as well as fault and performance management. These tasks take place at different time scales. Humans carry out a large share of long-term tasks, whereas computers execute usually real-time tasks. However, human intervention is also often necessary in the latter case to resolve failures and other difficult problems. These tasks involve often large amounts of data. For instance, a relatively static TDM network with 20 nodes and 40 links has already up to 1000 circuits. Short-lived circuits result in even more data. This large amount of data and their interdependencies guarantee that understanding a particular situation is a difficult and time consuming task (for both humans and computers).
Therefore, what is needed and is an object of the present invention is a means of creating and using an abstract, aggregated network-representation that suppresses irrelevant information and highlights the important information, thus reducing thinking time and search spaces of methods.
In addition, it is an object of the invention to make collaborative problem solving, involving humans and computers, feasible in more situations, which can be used to improve the quality of decisions.
Yet another object of the invention is to provide a means which generalizes the BIH abstraction, which overcomes the above-mentioned problems, and which can be applied to display the network status, to monitor the network, to determine routes, and to cost and price network usage.
Still another object of the invention is to provide a means of selecting routes which minimizes time and increases efficiency through the use of an abstract, aggregated network representation that suppresses irrelevant information and highlights important information, thus reducing thinking time and search spaces of methods.
Another object of the invention is to provide a concise graphical display of the possible routes or paths for different amounts of bandwidth xcex2, or some other restrictive cost measure, between the vertices of a network.
A computerized method facilitates reasoning about path selection in communication networks represented by a blocking island (xe2x80x9cBIxe2x80x9d) abstraction. The method takes a network graph as an input and computes a data structure of a Blocking Island Contour Map (xe2x80x9cBICMxe2x80x9d) by performing the following two actions. In a first action, links are ordered according to their free capacity. In a second action, in order to produce a hierarchy of abstract nodes and links, the links are processed as ordered, by performing the following four acts. In a first act, if a currently-processed link (the current link) is connected to a currently-processed abstract node (the current node) at the same free capacity level, the current link is added to the currently-processed abstract node. If the currently-processed link is no connected then a new abstract node that includes the current link is constructed, to which the current abstract node is set. In a second act, the network-graph-level end-points of the current link that are not already contained in an abstract node are included in the current abstract node. In a third act, the abstract nodes that contain an endpoint of the current link (and are at a higher free-capacity level) are included in the current abstract node. In a fourth act, the links which are connected to the current abstract node and which share the other abstract endpoint are aggregated, wherein, if such a set of links already contains abstract links at the free-capacity level of the current abstract node, these abstract links are merged and the yet-to-be aggregated links are included into the merged abstract link; otherwise, a new abstract link at the free-capacity level of the current abstract node and containing the yet-to-be aggregated abstract links is created. Finally, the BICM data structure is returned and can either be displayed by the method described below or utilized for applications like routing.
In another feature of the invention, the BICM may be computed for visual display by traversing the blocking island hierarchy from the leaves to the roots and drawing a closed line around the nodes contained in the current abstract node if (1) the current abstract node contains one or more network graph nodes or (2) the current abstract node contains more than one abstract node. If the drawn closed line encloses nodes that do not belong to the current abstract node, the display submethod draws one or more closed lines (of the same kind as the above one) around these nodes.
In another feature of the method of the invention, an incremental submethod takes a BICM data structure, a network link and a new free capacity value and uses these as inputs to update the BICM data structure by performing four actions. In a first action, the modified link is moved to an abstract node at the new free capacity level wherein the abstract node is an existing abstract node if there exists a link connected to the endpoints of the modified link at the new level, wherein, if there are multiple such abstract nodes, they are merged and the abstract nodes that contain these abstract nodes are merged recursively; wherein, if there is a single abstract node at a higher capacity level than the new capacity value, this abstract node is split into two new abstract nodes, this process continuing with the father of the split abstract node recursively; and wherein, if there is no existing abstract node, a new abstract node is created and included in the abstract node tree at the appropriate position. In a second action, each of the endpoints of the modified link is moved to the abstract node that contains the link connected to it with the largest free-capacity. In a third action, the abstract links that contain only one link are removed from the abstract link hierarchy and sets of links connected to modified abstract nodes that share the other abstract endpoint are aggregated into abstract links. In a fourth action, the abstract nodes that contain neither a network-graph node nor a network-graph link are removed from the abstract node hierarchy.
To facilitate reasoning about route selection in circuit- or packet-switched communication networks represented by a Blocking Island Contour Map. The method identifies the Blocking Island that contains both end-points of the demand and that has at least the demanded bandwidth. If such a Blocking Island exists, a path is computed in a hierarchical depth-first search manner. First, the Blocking Island is mapped to a Blocking Island Graph, with which the shortest path is computed. Second, the first step is applied recursively on each node of the computed path that is a Blocking Island and not a network graph node. For this purpose, the first step also maps aggregate (abstract) links connecting Blocking Islands. The shortest path submethod-is an extension of the Dijkstra algorithm. The extension consists of adding cost terms based on Blocking Island Contour Maps, namely, the cost of splitting (i.e., a weighted sum of the cost of all to-be-split Blocking Islands, if a route would use a particular network link) and for traversing Blocking Islands. The resulting shortest path submethod.
Computes the shortest, least restrictive and load-balanced path, where the relative weight of these three criteria is a parameter of the extended Dijkstra algorithm.